import { AbEqualToOther, Derivation, DerivationonSymbolEpsilon, DerivationonTokenEOF, EqualToEqualToOther, Grammar, GrammarToken, TokenEpsilon } from "./common_lr";
import { ContainerMarkableBox } from "./ContainerMarkableBox";
import { FamilyItemsLR0 } from "./lr0";

///////////////////////////////// LR(1) /////////////////////////////////



/**
 * 项目集规范族 LR(1) - 项目
 * 
 * A -> • B a    ⊸ $    pos = 0 ，展望符为 $
 * A ->  B • a   ⊸ $    pos = 1 ，展望符为 $
 * A ->  B a •   ⊸ $    pos = 2 ，展望符为 $
 */
 export class FamilyItemsLR1 extends FamilyItemsLR0 {
    readonly prospectSymbol: GrammarToken;
    constructor(d: Derivation, pos: number, prospectSymbol: GrammarToken) {
        super(d, pos);
        this.prospectSymbol = prospectSymbol;
    }
    
    equalToOther(other: FamilyItemsLR1): boolean {
        return super.equalToOther(other) && this.prospectSymbol === other.prospectSymbol;
    }

    static equal(a: FamilyItemsLR1, b: FamilyItemsLR1) {
        return EqualToEqualToOther(a, b);
    }

    toString(): string {
        const rightList: any = [...this.dervation.right];
        rightList.splice(this.pos, 0, "•");
        return `${this.dervation.left} -> ${rightList.join(" ")}   ⊸    ${this.prospectSymbol}`
    }
}


/**
 * 项目集规范族 LR(1) - 集合
 */
export class FamilyItemsSetLR1 implements AbEqualToOther {
    readonly container: FamilyItemsLR1[] = [];

    /**
     * 去重添加，如果重复则不添加
     * @param item 
     * @returns 成功添加返回真，否则，返回假
     */
    addItem(item: FamilyItemsLR1): boolean {
        for (const oi of this.container) {
            if (oi.equalToOther(item)) {
                return false;
            }
        }

        this.container.push(item);
        return true;
    }

    /**
     * 比较相等， 可以通过 Hash 优化
     * @TODO Hash 优化
     */
    equalToOther(other: FamilyItemsSetLR1): boolean {
        if (this === other) {
            return true;
        }

        if (other.container.length != this.container.length) {
            return false;
        }

        for (let idx = 0; idx < this.container.length; idx++) {
            const left = this.container[idx];
            const right = other.container[idx];
            if (!left.equalToOther(right)) {
                return false;
            }
        }
        return true;
    }

    static equal(a: FamilyItemsSetLR1, b: FamilyItemsSetLR1) {
        return EqualToEqualToOther(a, b);
    }

    toString(): string {
        return this.container.join("\n");
    }
}







/**
 * 项目集规范族 LR(1)
 */
 export class FamilyItemsTableLR1 {
    private g: Grammar;
    constructor(g: Grammar) {
        this.g = g;
    }

    private ExtendSetFrom(firstF: (tokenList: GrammarToken[]) => Set<GrammarToken>, srcList: FamilyItemsLR1[]): FamilyItemsSetLR1 {
        const box = new FamilyItemsSetLR1();
        const queue: FamilyItemsLR1[] = [];
        this.cachedDerivationMap = this.cachedDerivationMap ?? this.g.BuildDerivationMap();

        // add start
        for (const cd of srcList) {
            queue.push(cd);
        }

        while (queue.length > 0) {
            const head = queue.shift();
            if (!head) {
                throw new Error("BUG，不应为空");
            }
            if (!box.addItem(head)) {
                continue;
            }

            // 放入待求队列
            const token = head.facedToken;
            if (token?.IsNonTerminal) { // 非终结符
                const nmap = this.cachedDerivationMap.get(token);
                if (!nmap) {
                    throw new Error("BUG，输入的语法 G 定义错误");
                }
                const facedList = head.genFacedTokenList();
                facedList.shift(); // 移除第一个

                const thePallerTokens: GrammarToken[] = [];
                if (facedList.length == 0) { // 已经等于 0 了
                    thePallerTokens.push(head.prospectSymbol);
                } else {
                    const sgg = firstF(facedList);
                    sgg.delete(DerivationonSymbolEpsilon);
                    sgg.forEach(item =>  thePallerTokens.push(item)  );
                }

                for (let nitem of nmap.values()) {
                    for (const token of thePallerTokens) {
                        queue.push(new FamilyItemsLR1(nitem, 0, token));
                    }
                }
            }
        }

        return box;
    }

    cachedDerivationMap: Map<GrammarToken, Set<Derivation>> | null = null;

    /**
     * 重新计算语法相关信息
     */
    ReclaculateInfo(): ContainerMarkableBox<FamilyItemsSetLR1, GrammarToken> {
        this.cachedDerivationMap = this.g.BuildDerivationMap();
        const firstF = this.g.CalcuateNonTerminatorFirstFunc();


        // 计算项目集规范组
        // 第一项 start d list
        const theFirstItemSet = this.ExtendSetFrom(
            firstF,
            [...this.cachedDerivationMap.get(this.g.s) ?? []]
                .map(item => new FamilyItemsLR1(item, 0, DerivationonTokenEOF))
        );

        // map box
        const theMapBox = new ContainerMarkableBox<FamilyItemsSetLR1, GrammarToken>(
            FamilyItemsSetLR1.equal,
            (a, b) => a === b,
            theFirstItemSet,
        );

        // dui 
        const candicateList: FamilyItemsSetLR1[] = [theFirstItemSet];

        while (candicateList.length > 0) {
            const candicate = candicateList.shift() ?? theFirstItemSet;

            // next...
            for (let ifToken of [...this.g.vt, ...this.g.vn]) {

                // 构造某个项目的初始……
                const list: FamilyItemsLR1[] = [];
                for (let item of candicate.container) {
                    if (item.isShift() && item.facedToken == ifToken) { // 可以向后移入
                        list.push(new FamilyItemsLR1(item.dervation, item.pos + 1, item.prospectSymbol));
                    }
                }

                if (list.length > 0) {
                    const theBuiledSet = this.ExtendSetFrom(firstF, list);
                    const added = theMapBox.addNodeByEdge(candicate, ifToken, theBuiledSet);
                    if (added) {
                        candicateList.push(theBuiledSet);
                    }
                }
            }

            // ngg
        }

        return theMapBox;
    }

    static FromGrama(g: Grammar): FamilyItemsTableLR1 {
        var f = new FamilyItemsTableLR1(g);
        f.ReclaculateInfo();
        return f;
    }
}

